package com.leetcode.No1838;

import org.junit.Test;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: leetcode
 * @description: 最高频元素的频数
 * @author: wangzhihua
 * @date: 2021-07-19
 */
public class Solution02 {

	@Test
	public void test01() throws IOException {
		String fileNme = "C:/Users/Louzen/Desktop/xx.txt";
		File file = new File(fileNme);
		FileInputStream inputStream = new FileInputStream(file);
		byte[] bytes = new byte[10240];
		int num;
		StringBuilder sb = new StringBuilder();
		while ((num = inputStream.read(bytes)) > 0) {
			String s = new String(bytes, 0, num);
			sb.append(s);
		}
		String str = sb.toString();
//		System.out.println(str);
		String[] strArray = str.split(",");
		List<Integer> intList = new ArrayList<Integer>();
		for (String ss : strArray) {
			intList.add(Integer.parseInt(ss));
		}
		int[] nums = new int[intList.size()];
		for (int i = 0; i < intList.size(); ++i) {
			nums[i] = intList.get(i);
		}
		System.out.println(maxFrequency(nums, 100000));
	}

	public int maxFrequency(int[] nums, int k) {
		Arrays.sort(nums);

		int previousIndex = 0;
		int usedK = 0; // <= k
		int tmpAns = 1;
		int ans = 1;
		for (int i = 1; i < nums.length; ++i) {
			usedK += (i - previousIndex) * (nums[i] - nums[i - 1]);
			if (usedK <= k) {
				ans = Math.max(ans, ++tmpAns);
				continue;
			}
			while (previousIndex < i && usedK > k) {
				usedK -= nums[i] - nums[previousIndex++];
			}
			tmpAns = i - previousIndex + 1;
		}
		return ans;
	}

	public void sort(int[] nums, int left, int right) {
		if (nums == null || nums.length <= 1 || left >= right) {
			return;
		}
		int anchorNum = nums[left];
		int anchorLeft = left;
		int anchorRight = right;
		do {
			while (left < right && anchorNum <= nums[right]) {
				--right;
			}
			nums[left] = nums[right];
			while (left < right && nums[left] <= anchorNum) {
				++left;
			}
			nums[right] = nums[left];
		} while (left < right);
		// 此时left=right
		nums[left] = anchorNum;
		sort(nums, anchorLeft, right - 1);
		sort(nums, left + 1, anchorRight);
	}

}
